home *** CD-ROM | disk | FTP | other *** search
/ Graphics Plus / Graphics Plus.iso / general / procssng / compstol / cmpsttl1.lha / CompositeTool / v1.1.dist / HDF / dfimcomp.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-05-08  |  34.5 KB  |  1,229 lines
  1. /*****************************************************************************
  2. * 
  3. *              NCSA HDF version 3.00
  4. *                December, 1989
  5. *
  6. * NCSA HDF Version 3.00 source code and documentation are in the public
  7. * domain.  Specifically, we give to the public domain all rights for future
  8. * licensing of the source code, all resale rights, and all publishing rights.
  9. * 
  10. * We ask, but do not require, that the following message be included in all
  11. * derived works:
  12. * 
  13. * Portions developed at the National Center for Supercomputing Applications at
  14. * the University of Illinois at Urbana-Champaign.
  15. * 
  16. * THE UNIVERSITY OF ILLINOIS GIVES NO WARRANTY, EXPRESSED OR IMPLIED, FOR THE
  17. * SOFTWARE AND/OR DOCUMENTATION PROVIDED, INCLUDING, WITHOUT LIMITATION,
  18. * WARRANTY OF MERCHANTABILITY AND WARRANTY OF FITNESS FOR A PARTICULAR PURPOSE
  19. * 
  20. *****************************************************************************/
  21.  
  22. /************************************************************************/
  23. /*  Module Name : imcomp                        */
  24. /*  Exports     : DFCimcomp(), DFCunimcomp()                */
  25. /*  Purpose     : Compresses color images               */
  26. /*  Author  : Eng-Kiat Koh                      */
  27. /*  Date    : June 30th, 1988                   */
  28. /*  Functions   : DFCimcomp(), compress(), init_global(), cnt_color()   */
  29. /*        set_palette(), fillin_color(), map(), nearest_color() */
  30. /*        DFCunimcomp(), sqr()                                  */
  31. /************************************************************************/
  32.  
  33.  
  34. #include "df.h"
  35.  
  36. #define PALSIZE 256
  37. #define BIT8 0
  38. #define BIT24 1
  39.  
  40. #ifndef MAC
  41. #define MAXCOLOR 32768
  42. #else /*MAC*/
  43. #define MAXCOLOR 768
  44. #endif /*MAC*/
  45.  
  46. #define RED 0
  47. #define GREEN 1
  48. #define BLUE 2
  49. #define EPSILON 0.5
  50. #define LO 1
  51. #define HI 0
  52.  
  53. struct rgb
  54. {
  55.   char c[3];
  56. };
  57.  
  58. struct box
  59. {
  60.   float bnd[3][2];
  61.   int *pts;
  62.   int nmbr_pts;
  63.   int nmbr_distinct;
  64.   struct box *left;
  65.   struct box *right;
  66. };
  67.  
  68.  
  69. char *new_pal;          /* pointer to new palette           */
  70.  
  71.  
  72. static int *hist;                /* histogram for distinct colors    */
  73. static struct box *frontier;     /* pointer to the list of boxes     */
  74. static struct rgb *distinct_pt;  /* contains all distinct rgb points */
  75.  
  76. static void sel_palette();
  77. static void compress();
  78. static void init_global();
  79. static int cnt_color();
  80. static void set_palette();
  81. static void fillin_color();
  82. static int indx();
  83. static void map();
  84. static int nearest_color();
  85. static long int sqr();
  86. static void init();
  87. static int partition();
  88. static struct box *find_box();
  89. static void split_box();
  90. static void assign_color();
  91. static int select_dim();
  92. static float find_med();
  93. static void classify();
  94. static int next_pt();
  95.  
  96. extern char *calloc();
  97.  
  98. static struct rgb *color_pt;    /* contains the hi-lo colors for each block */
  99. static char *image;        /* contains the compressed image            */
  100. static int trans[MAXCOLOR];     /* color translation table                  */
  101.  
  102. /************************************************************************/
  103. /*  Function    : DFCimcomp                                             */
  104. /*  Purpose : Performs Imcomp Compression                           */
  105. /*  Parameters  :                                                       */
  106. /*    xdim, ydim - dimensions of image                                  */
  107. /*                 IT IS ASSUMED THAT THE DIMENSIONS ARE A MULTIPLE OF 4*/
  108. /*    in, out    - input image array and output image buffer size of in */
  109. /*                 is xdim*ydim bytes for 8 bit per pixel mode. It is 3 */
  110. /*                 times that for 24 bits per pixel mode. The output    */
  111. /*                 buffer is always (xdim*ydim)/4.                      */
  112. /*    in_pal     - input palette. Consist of rgb triples unlike seq-type*/
  113. /*                 palette. This is a NULL pointer if operating at the  */
  114. /*                 24 bit per pixel mode.                               */
  115. /*    out_pal    - output palette. Consist of PALSIZE color entries.    */
  116. /*                 each entry is an rgb triple.                         */
  117. /*    mode       - Either BIT8 or BIT24                                 */
  118. /*  Returns     : none                          */
  119. /*  Called by   : External routines                                     */
  120. /*  Calls       : init_global(), compress(), cnt_color(), set_palette(),*/
  121. /*        sel_palette(), map()                                  */
  122. /************************************************************************/
  123.  
  124. void DFCimcomp(xdim, ydim, in, out, in_pal, out_pal, mode)
  125. int32 xdim, ydim;
  126. int mode;
  127. char in[], out[], in_pal[], out_pal[];
  128. {
  129.   char raster[48];
  130.   int blocks, nmbr, i, j, k, l, x, y;
  131.   void init_global();
  132.   void compress();
  133.   int cnt_color();
  134.   void set_palette();
  135.   void sel_palette();
  136.   void map();
  137.   void fillin_color();
  138.  
  139.   init_global(xdim, ydim, out, out_pal);
  140.  
  141.   /* compress pixel blocks */
  142.   blocks = 0;
  143.   for (i=0; i<(ydim/4); i++)
  144.     for (j=0; j<(xdim/4); j++)
  145.     {
  146.       switch (mode)
  147.       {
  148.         case BIT8 : /* 8 bit per pixel format */
  149.             k = 0;
  150.             for (y=(i*4); y<(i*4+4); y++)
  151.               for (x=(j*4); x<(j*4+4); x++)         
  152.               {
  153.             l = y*xdim + x;
  154.             raster[k++] = in_pal[3*in[l]];
  155.             raster[k++] = in_pal[3*in[l]+1];
  156.             raster[k++] = in_pal[3*in[l]+2];
  157.               } /* end of for x */
  158.             compress(raster,blocks);
  159.             break;
  160.  
  161.     case BIT24: /* 24 bit per pixel format */
  162.             k = 0;
  163.             for (y=(i*4); y<(i*4+4); y++)
  164.               for (x=(j*4); x<(j*4+4); x++)         
  165.               {
  166.             l = 3 *(y*xdim + x);
  167.             raster[k++] = in[l];
  168.             raster[k++] = in[l+1];
  169.             raster[k++] = in[l+2];
  170.               } /* end of for x */
  171.             compress(raster,blocks);
  172.             break;
  173.     
  174.     default   : /* unsupported format */
  175.             printf("Error : Unsupported Format \n");
  176.             exit(1);
  177.             break;
  178.       } /* end of switch */
  179.       
  180.       blocks++;
  181.     } /* end of for j */
  182.  
  183.   /* set palette */
  184.   nmbr = cnt_color(blocks);
  185. /*
  186.   printf("Number of colors %d \n", nmbr);
  187. */
  188.   if (nmbr <= PALSIZE)
  189.     set_palette(blocks);
  190.   else
  191.   {
  192.     sel_palette(blocks,nmbr,color_pt);
  193.     map(blocks);
  194.   }
  195.  
  196.   fillin_color(blocks);
  197.  
  198. } /* end of DFCimcomp */
  199.  
  200.  
  201.  
  202.  
  203.  
  204.  
  205. /************************************************************************/
  206. /*  Function    : compress                                  */
  207. /*  Purpose : Given a block of 16 pixels, sets up a 16 bit bitmap   */
  208. /*                and assigns a lo and hi color for the block. For block*/
  209. /*                i, hi color is stored in color_pt[2i] and lo in       */
  210. /*                color_pt[2i+1]. Each color is then reduced to 15 bits */
  211. /*                by truncating the lower order 3 bits of each component*/
  212. /*  Parameter   :                           */
  213. /*    raster     - contains the 16 pixels of a block. Each pixel is 3   */
  214. /*         bytes, 1 byte for each color component               */
  215. /*    block  - pixel block number                                   */
  216. /*  Returns     : none                                                  */
  217. /*  Called by   : DFCimcomp()                       */
  218. /*  Calls       : none                          */
  219. /************************************************************************/
  220.  
  221. static void compress(raster, block)
  222. char raster[];
  223. int block;
  224. {
  225.   float y[16], y_av;
  226.   int i, j, k, l, bit;
  227.   int high, hi, lo;
  228.   int c_hi[3], c_lo[3];
  229.  
  230.   /* calculate luminance */
  231.   y_av = 0.0;
  232.   for (i=0; i<16; i++)
  233.   {
  234.     j = 3*i;
  235.     y[i] = 0.3*(float)raster[j] + 0.59*(float)raster[j+1] + 
  236.            0.11*(float)raster[j+2];
  237. /*    printf("compress: y[%d] is %f\n",i,y[i]);*/
  238.     y_av = y_av + y[i];
  239.   }
  240.   y_av = y_av / 16.0;
  241. /*  printf("y_av is %f\n",y_av); */
  242.  
  243.   /* initialize c_hi and c_lo */
  244.   for (i=RED; i<=BLUE; i++)
  245.   {
  246.     c_hi[i] = 0;
  247.     c_lo[i] = 0;
  248.   }
  249.  
  250.   /* build bit map */
  251.   k = 4 * block;
  252.   high = 0;
  253.   hi = 2 * block;
  254.   lo = hi + 1;
  255.   for (i=0; i<2; i++)
  256.   {
  257.     bit = 128;
  258.     for (j = (i*8); j<(i*8+8); j++)
  259.     {
  260.       if (y[j] > y_av)
  261.       {
  262.     image[k] = image[k] | bit;
  263.     high++;
  264.         for (l=RED; l<= BLUE; l++)
  265.       c_hi[l] = c_hi[l] + (int)raster[3*j+l];
  266.       }
  267.       else
  268.       {
  269.     for (l=RED; l<=BLUE; l++)
  270.           c_lo[l] = c_lo[l] + (int)raster[3*j+l];
  271.       } /* end of if */
  272.  
  273.       bit = bit >> 1;
  274.     } /* end of for j */
  275.    
  276.     k++;
  277.   } /* end of for i */
  278.  
  279.   /* calculate hi lo color */
  280.   for (i=RED; i<=BLUE; i++)
  281.   {
  282.     if (high != 0)
  283.       color_pt[hi].c[i] = (int)((float)c_hi[i] / (float)high);
  284.     if (high != 16)
  285.       color_pt[lo].c[i] = (int)((float)c_lo[i] / (float)(16 - high));
  286.     color_pt[hi].c[i] = color_pt[hi].c[i] >> 3;
  287.     color_pt[lo].c[i] = color_pt[lo].c[i] >> 3;
  288.  
  289.   }
  290. } /* end of compress */
  291.  
  292.  
  293.  
  294.  
  295.  
  296.  
  297. /************************************************************************/
  298. /*  Function    : init_global                       */
  299. /*  Purpose : Allocates memory for global variables                 */
  300. /*  Parameter   :                           */
  301. /*    xdim, ydim - x and y dimension of image               */
  302. /*    out        - pointer to output buffer                             */
  303. /*    out_pal    - pointer to output palette                            */
  304. /*  Returns     : none                              */
  305. /*  Called by   : DFCimcomp()                       */
  306. /*  Calls       : none                          */
  307. /************************************************************************/
  308.  
  309. static void init_global(xdim, ydim, out, out_pal)
  310. int32 xdim, ydim;
  311. char *out, *out_pal;
  312. {
  313.   int i, j;
  314.  
  315.   /* allocate memory */
  316.   image = out;
  317.   new_pal = out_pal;
  318.   color_pt = (struct rgb *)calloc((unsigned)((xdim*ydim)/8),
  319.          sizeof(struct rgb));
  320.  
  321.   if (image == NULL || color_pt == NULL || new_pal == NULL)
  322.   {
  323.     printf("Error : Out of Memory\n");
  324.     exit(1);
  325.   }
  326.  
  327.   /* initialize */
  328.   for (i=0; i<(xdim*ydim/4); i++)
  329.     image[i] = 0;
  330.  
  331.   for (i=0; i<(xdim*ydim/8); i++)
  332.     for (j=RED; j<= BLUE; j++)
  333.       color_pt[i].c[j] = 0;
  334.  
  335.   for (i=0; i<MAXCOLOR; i++)
  336.     trans[i] = -1;
  337. } /* end of init_global */
  338.  
  339.  
  340.  
  341.  
  342.  
  343. /************************************************************************/
  344. /*  Function    : cnt_color                                 */
  345. /*  Purpose : Counts the number of distinct colors compressd image  */
  346. /*  Parameter   :                           */
  347. /*    blocks     - total number of pixel blocks             */
  348. /*  Returns     : Number of distinct colors                             */
  349. /*  Called by   : DFCimcomp()                                           */
  350. /*  Calls       : indx()                        */
  351. /************************************************************************/
  352.  
  353. static int cnt_color(blocks)
  354. int blocks;
  355. {
  356.   int temp[MAXCOLOR];
  357.   int i, k, count;
  358.   int indx();
  359.  
  360.   for (i=0; i<MAXCOLOR; i++)
  361.     temp[i] = -1;
  362.  
  363.   for (i=0; i<(2*blocks); i++)
  364.   {
  365.     k = indx(color_pt[i].c[RED],color_pt[i].c[GREEN],color_pt[i].c[BLUE]);
  366. /*    printf("cnt_color: k is %d\n",k); */
  367.     temp[k] = 0;
  368.   }
  369.  
  370.   count  = 0;
  371.   for (i = 0; i< MAXCOLOR; i++)
  372.     if (temp[i] == 0)
  373.       count++;
  374.  
  375.   return count;
  376. } /* end of cnt_color */
  377.  
  378.  
  379.  
  380.  
  381.  
  382. /************************************************************************/
  383. /*  Function    : set_palette                       */
  384. /*  Purpose : The number of distinct colors is less than the desired*/
  385. /*                output palette size. Therefore each distinct color can*/
  386. /*        be a palette entry. Function enters each distinct     */
  387. /*                color as a palette entry and sets up the translation  */
  388. /*                table. It also shifts each color component left 3 bits*/
  389. /*                so that each color component is again 8 bits wide     */
  390. /*  Parameter   :                           */
  391. /*    blocks     - total number of pixel blocks                         */
  392. /*  Returns     : none                          */
  393. /*  Called by   : DFCimcomp()                       */
  394. /*  Calls       : indx()                        */
  395. /************************************************************************/
  396.  
  397. static void set_palette(blocks)
  398. int blocks;
  399. {
  400.   int ent, i, k;
  401.   int indx();
  402.  
  403.   ent = 0;
  404.   for (i = 0; i<(2*blocks); i++)
  405.   {
  406.     k = indx(color_pt[i].c[RED],color_pt[i].c[GREEN],color_pt[i].c[BLUE]);
  407.     if (trans[k] == -1)
  408.     {
  409.       new_pal[3*ent] = color_pt[i].c[RED] << 3;
  410.       new_pal[3*ent+1] = color_pt[i].c[GREEN] << 3;
  411.       new_pal[3*ent+2] = color_pt[i].c[BLUE] << 3;  
  412.       trans[k] = ent;
  413.       ent++;
  414.     }
  415.   }
  416. } /* end of set_palette */
  417.  
  418.  
  419.  
  420.  
  421.  
  422. /************************************************************************/
  423. /*  Function    : fillin_color                      */
  424. /*  Purpose : For each pixel block, fills in the pointers into the  */
  425. /*                palette.                                              */
  426. /*  Parameter   :                           */
  427. /*    blocks     - total number of pixel blocks             */
  428. /*  Returns     : none                          */
  429. /*  Called by   : DFCimcomp()                       */
  430. /*  Calls       : none                          */
  431. /************************************************************************/
  432.  
  433. static void fillin_color(blocks)
  434. int blocks;
  435. {
  436.   int i, j, k;
  437.  
  438.   for (i=0; i<blocks; i++)
  439.     for (j=HI; j<=LO; j++)
  440.     {
  441.       k = indx(color_pt[2*i+j].c[RED],color_pt[2*i+j].c[GREEN],
  442.            color_pt[2*i+j].c[BLUE]);
  443.       image[i*4+2+j] = trans[k];
  444.     }
  445. } /* end of fillin_color */
  446.  
  447.  
  448.  
  449.  
  450.  
  451. /************************************************************************/
  452. /*  Function    : indx                          */
  453. /*  Purpose : Maps an rgb triple (5 bits each) to an integer array  */
  454. /*        index                         */
  455. /*  Parameter   :                           */
  456. /*    r, g, b    - color components                 */
  457. /*  Returns     : returns an array index                */
  458. /*  Called by   : set_palette(), fillin_color(), map()                  */
  459. /*  Calls       : none                          */
  460. /************************************************************************/
  461.  
  462. static int indx(r, g, b)
  463. char r, g, b;
  464. {
  465.   int temp;
  466.  
  467.   temp = 0;
  468.   temp = (r << 10) | (g  << 5) | b ;
  469.   return temp;
  470. } /* end of indx */
  471.  
  472.  
  473.  
  474.  
  475.  
  476.  
  477. /************************************************************************/
  478. /*  Function    : map                           */
  479. /*  Purpose : Maps a color_pt to the closest representative color   */
  480. /*        Sets up translation table             */
  481. /*  Parameter   :                           */
  482. /*    blocks     - total number of pixel blocks             */
  483. /*  Returns     : none                          */
  484. /*  Called by   : DFCimcomp()                       */
  485. /*  Calls       : nearest_color()                   */
  486. /************************************************************************/
  487.  
  488. static void map(blocks)
  489. int blocks;
  490. {
  491.   int i, k;
  492.   int r, g, b;
  493.   int indx();
  494.   int nearest_color();
  495.  
  496.   for (i=0; i<(2*blocks); i++)
  497.   {
  498.     k = indx(color_pt[i].c[RED], color_pt[i].c[GREEN], color_pt[i].c[BLUE]);
  499.  
  500.     if (trans[k] == -1)
  501.     {
  502.       r = color_pt[i].c[RED]<<3;
  503.       g = color_pt[i].c[GREEN]<<3;
  504.       b = color_pt[i].c[BLUE]<<3;
  505.       trans[k] = nearest_color(r, g, b);
  506. /*
  507.       printf("map: %d %d %d mapped to %d %d %d\n", r, g, b, new_pal[trans[k]*3],
  508.           new_pal[trans[k]*3+1], new_pal[trans[k]*3+2]);
  509. */
  510.     }
  511.   }
  512. } /* end of map */
  513.   
  514.  
  515.  
  516.  
  517. /************************************************************************/
  518. /*  Function    : nearest_color                     */
  519. /*  Purpose : Finds the nearest palette color           */
  520. /*  Parameter   :                           */
  521. /*    r, g, b    - color component                  */
  522. /*  Returns     : Entry number of the closest color in the palette      */
  523. /*  Called by   : map()                         */
  524. /*  Calls       : sqr()                         */
  525. /************************************************************************/
  526.  
  527. static int nearest_color(r, g, b)
  528. char r, g, b;
  529. {
  530.   int i, near; 
  531.   long int min, error;
  532.   long int sqr();
  533.  
  534.   min = sqr(r-new_pal[0]) + sqr(g-new_pal[1]) + sqr(b-new_pal[2]);
  535.   near = 0;
  536.   for (i=1; i<PALSIZE; i++)
  537.   {
  538.     error = sqr(r-new_pal[3*i]) + sqr(g-new_pal[3*i+1]) + 
  539.         sqr(b-new_pal[3*i+2]);
  540.     if (error < min)
  541.     {
  542.     min = error;
  543.         near = i;
  544.     }
  545.   }
  546.  
  547.   return near;
  548. } /* end of nearest_color */
  549.  
  550.  
  551.  
  552.  
  553. /************************************************************************/
  554. /*  Function    : sqr                           */
  555. /*  Purpose : Computes the square of an integer         */
  556. /*  Parameter   :                           */
  557. /*    x      - an integer                       */
  558. /*  Returns     : The square of x                   */
  559. /*  Called by   : nearest_color()                   */
  560. /*  Calls       : none                          */
  561. /************************************************************************/
  562.  
  563. static long int sqr(x)
  564. int x;
  565. {
  566.   return (x*x);
  567. }
  568.  
  569.  
  570.  
  571.  
  572.  
  573. /************************************************************************/
  574. /*  Function    : DFCunimcomp                       */
  575. /*  Purpose : 'Decompresses' the compressed image           */
  576. /*  Parameter   :                           */
  577. /*    xdim, ydim - dimensions of image                  */
  578. /*    in, out    - Input buffer and output buffer. Size of input buffer */
  579. /*         is (xdim*ydim)/4. Size of output buffer is 4 times   */
  580. /*         that. It 'restores' images into seq-type files       */
  581. /*  Returns     : none                          */
  582. /*  Called by   : External routines                 */
  583. /*  Calls       : none                          */
  584. /************************************************************************/
  585.  
  586. void DFCunimcomp(xdim, ydim, in, out)
  587. int32 xdim, ydim;
  588. char in[], out[];
  589. {
  590.   int bitmap, temp;
  591.   int i, j, k, x, y;
  592.   char hi_color, lo_color;
  593.  
  594.   for (y=0; y<(ydim/4); y++)
  595.     for (x=0; x<xdim; x=x+4)
  596.     {
  597.       k = y*xdim + x;
  598.       hi_color = in[k+2]; 
  599.       lo_color = in[k+3];
  600.  
  601.       bitmap = (in[k] << 8) | in[k+1];
  602.  
  603.       for (i=(y*4); i<(y*4+4); i++)
  604.       {
  605.         temp = bitmap >> (3 + y*4 - i)*4;
  606.         for (j=x; j<(x+4); j++)
  607.         {
  608.       if ((temp & 8) == 8)
  609.         out[i*xdim+j] = hi_color;
  610.       else
  611.         out[i*xdim+j] = lo_color;
  612.       temp = temp << 1;
  613.     }
  614.       }
  615.     } /* end of for x */
  616. } /* end of DFCunimcomp */
  617.  
  618.  
  619.  
  620. /************************************************************************/
  621. /*  Module Name : color                         */
  622. /*  Exports     : sel_palette(); new_pal, pointer to a new color palette*/
  623. /*  Purpose     : Quantizes colors                  */
  624. /*  Author  : Eng-Kiat Koh                      */
  625. /*  Date    : June 30th, 1988                   */
  626. /*  Functions   : sel_palette(), init(), sort(), partition(), find_box()*/
  627. /*        split_box(), assign_color(), select_dim(), find_med() */
  628. /*                classify(), next_pt()                                 */
  629. /************************************************************************/
  630.  
  631.  
  632.  
  633.  
  634.  
  635.  
  636.  
  637. /************************************************************************/
  638. /*  Function    : sel_palette                       */
  639. /*  Purpose : Selects PALSIZE palette colors out of a list of colors*/
  640. /*        in color_pt                       */
  641. /*  Parameter   :                           */
  642. /*    blocks     - number of pixel blocks               */
  643. /*    distinct   - number of distinct colors                */
  644. /*    color_pt   - contains the lo hi colors for each pixel block       */
  645. /*  Returns     : none                          */
  646. /*  Called by   : DFCimcomp()                       */
  647. /*  Calls       : init(), split_box(), find_box(), assign_color()   */
  648. /************************************************************************/
  649.  
  650. static void sel_palette(blocks,distinct, color_pt)
  651. int blocks, distinct;
  652. struct rgb *color_pt;
  653. {
  654.   int boxes;
  655. /*  int i, j;*/
  656.   struct box *ptr;
  657.   struct box *find_box();
  658.   void init();
  659.   void split_box();
  660.   void assign_color();
  661.  
  662.   init(blocks, distinct, color_pt);
  663.  
  664.   /* split box into smaller boxes with about equal number of points */
  665.   for (boxes=1; boxes < PALSIZE; boxes++)
  666.   {
  667. /*
  668.     ptr=frontier->right;
  669.     j = 0;
  670.     while (ptr != NULL)
  671.     {
  672.       printf("Box %d, distinct %d, total %d\n",j,ptr->nmbr_distinct,
  673.              ptr->nmbr_pts);
  674.       for (i=0; i<ptr->nmbr_distinct; i++)
  675.         printf("pt %d: %d %d %d",i,distinct_pt[ptr->pts[i]].c[RED],
  676.                 distinct_pt[ptr->pts[i]].c[GREEN], 
  677.             distinct_pt[ptr->pts[i]].c[BLUE]);
  678.       j++;
  679.       ptr = ptr->right;
  680.     }
  681. */
  682.  
  683.     ptr = find_box();
  684.     split_box(ptr);
  685.   } 
  686.  
  687.   assign_color();
  688. }
  689.  
  690.  
  691.  
  692.  
  693.  
  694.  
  695. /************************************************************************/
  696. /*  Function    : init                          */
  697. /*  Purpose : Initializes the global variables, sets up the first   */
  698. /*        box. It will contain all the color points     */
  699. /*  Parameter   :                           */
  700. /*    blocks     - number of pixel blocks               */
  701. /*    distinct   - number of distinct colors                */
  702. /*    color_pt   - contains the lo hi colors for each pixel block       */
  703. /*  Returns     : none                          */
  704. /*  Called by   : sel_palette()                     */
  705. /*  Calls       : none                          */
  706. /************************************************************************/
  707.  
  708. static void init(blocks, distinct, color_pt)
  709. int blocks, distinct;
  710. struct rgb *color_pt;
  711. {
  712.   int i, j, k, l;
  713.   int temp[MAXCOLOR];
  714.   struct box *first;
  715.   struct box *dummy;
  716.  
  717.   /* alloc memory */
  718.   hist = (int *)calloc((unsigned)distinct,sizeof(int));
  719.   distinct_pt = (struct rgb *)calloc((unsigned)distinct,sizeof(struct rgb));
  720.  
  721.   for (i=0; i<distinct; i++)
  722.     hist[i] = 0;
  723.  
  724.  
  725.   /* select distinct pts and set up histogram */
  726.   for (i=0; i<MAXCOLOR; i++)
  727.     temp[i] = -1;
  728.  
  729.   k = 0;
  730.   for (i=0; i<(2*blocks); i++)
  731.   {
  732.     j = (color_pt[i].c[RED] << 10) | (color_pt[i].c[GREEN] << 5) |
  733.         color_pt[i].c[BLUE];
  734.  
  735.     if (temp[j] == -1)
  736.     {
  737.       /* new pt */
  738.       temp[j] = k;
  739.       for (l=RED; l<=BLUE; l++)
  740.     distinct_pt[k].c[l] = color_pt[i].c[l];
  741.       k++;
  742.    }
  743.  
  744.    hist[temp[j]]++;
  745.   }
  746.  
  747.       
  748.   /* set up first box */
  749.   first = (struct box *)malloc(sizeof(struct box));
  750.   for (i=RED; i<=BLUE; i++)
  751.   {
  752.     first->bnd[i][LO] = 999.9;
  753.     first->bnd[i][HI] = -999.9;
  754.  
  755.     for (j=0; j<distinct; j++)
  756.     {
  757.       if (first->bnd[i][LO] > (float)distinct_pt[j].c[i])
  758.     first->bnd[i][LO] = (float)distinct_pt[j].c[i];
  759.  
  760.       if (first->bnd[i][HI] < (float)distinct_pt[j].c[i])
  761.     first->bnd[i][HI] = (float)distinct_pt[j].c[i];
  762.     } /* end of for j */
  763.  
  764.     first->bnd[i][LO] = first->bnd[i][LO] - EPSILON;
  765.     first->bnd[i][HI] = first->bnd[i][HI] + EPSILON;
  766.   } /* end of for i */
  767.  
  768.   first->pts = (int *)calloc((unsigned)distinct,sizeof(int));
  769.   for (i=0; i<distinct; i++)
  770.     first->pts[i] = i;
  771.   first->nmbr_pts = 2*blocks;
  772.   first->nmbr_distinct = distinct;
  773.  
  774.   dummy = (struct box *)malloc(sizeof(struct box));
  775.   frontier = dummy;
  776.   dummy->right = first;
  777.   first->left = dummy;
  778.   first->right = NULL;
  779.   dummy->nmbr_pts = 0;
  780. } /* end of init */
  781.  
  782.  
  783.  
  784.  
  785.  
  786.  
  787.  
  788. /************************************************************************/
  789. /*  Function    : sort                          */
  790. /*  Purpose : Performs quick sort on the points in a box along a    */
  791. /*        given dimension                   */
  792. /*  Parameter   :                           */
  793. /*    l, r   - index of leftmost and rightmost element      */
  794. /*    dim    - dimension along which sorting is done        */
  795. /*    rank   - an array which carries the index of the points to be */
  796. /*         sorted                       */
  797. /*  Returns     : none                          */
  798. /*  Called by   : find_med()                        */
  799. /*  Calls       : partition()                       */
  800. /************************************************************************/
  801.  
  802. static void sort(l,r,dim, rank)
  803. int l, r, dim, rank[];
  804. {
  805.   int i;
  806.   int partition();
  807.   void sort();
  808.  
  809.   if (r > l)
  810.   {
  811.     i = partition(l, r, dim, rank);
  812.     sort(l, i-1, dim, rank);
  813.     sort(i+1, r, dim, rank);
  814.   }
  815. }
  816.  
  817.  
  818.  
  819.  
  820.  
  821.  
  822. /************************************************************************/
  823. /*  Function    : partition                     */
  824. /*  Purpose : Partitions the list into 2 parts as in the quick sort */
  825. /*        algorithm                     */
  826. /*  Parameter   :                           */
  827. /*    l, r   - index of leftmost and rightmost element      */
  828. /*    dim    - dimension along which sorting is done        */
  829. /*    rank   - an array which carries the index of the points to be */
  830. /*  Returns     : index where list is partitioned           */
  831. /*  Called by   : sort()                        */
  832. /*  Calls       : none                          */
  833. /************************************************************************/
  834.  
  835. static int partition(l, r, dim, rank)
  836. int l, r, dim, rank[];
  837. {
  838.   int i, j, temp;
  839.   char v;
  840.   
  841.   v = distinct_pt[rank[r]].c[dim];
  842.   i = l-1;
  843.   j = r;
  844.  
  845.   /* repeat until i and j crosses */
  846.   do
  847.   {
  848.     /* repeat until an element >= v is found */
  849.     do
  850.       i++;
  851.     while (distinct_pt[rank[i]].c[dim] < v);
  852.  
  853.     /* repeat until an element <= v is found */
  854.     do
  855.       j--;
  856.     while ((j>0) && (distinct_pt[rank[j]].c[dim] > v));
  857.  
  858.     /* swap pointers */
  859.     temp = rank[i];
  860.     rank[i] = rank[j];
  861.     rank[j] = temp;
  862.   }
  863.   while (i < j);
  864.  
  865.   /* position partitioning element at location i */
  866.   temp = rank[j];
  867.   rank[j] = rank[i];
  868.   rank[i] = rank[r];
  869.   rank[r] = temp;
  870.  
  871.   return i;
  872. }
  873.  
  874.  
  875.  
  876.  
  877.  
  878. /************************************************************************/
  879. /*  Function    : find_box                      */
  880. /*  Purpose : Finds the box with the largest number of color points */
  881. /*        The points need not necessarily be distinct. But in   */
  882. /*        order to partition the box, there must be at least  2 */
  883. /*        distinct points                   */
  884. /*  Parameter   : none                          */
  885. /*  Returns     : pointer to box selected for splitting         */
  886. /*  Called by   : sel_palette()                     */
  887. /*  Calls       : none                          */
  888. /************************************************************************/
  889.  
  890. static struct box *find_box()
  891. {
  892.   struct box *temp;
  893.   struct box *max;
  894.   int max_pts;
  895.  
  896.   max_pts = 1;
  897.   max = NULL;
  898.   temp = frontier->right;
  899.   while (temp != NULL)
  900.     if ((temp->nmbr_distinct > 1) && (max_pts < temp->nmbr_pts))
  901.     {
  902.       max_pts = temp->nmbr_pts;
  903.       max = temp;
  904.       temp = temp->right;
  905.     }
  906.     else
  907.       temp = temp->right;
  908.  
  909.   if (max == NULL)
  910.   {
  911.     printf("Error : Number of color points < palette \n");
  912.     exit(1);
  913.   }
  914.  
  915.   return max;
  916. }
  917.  
  918.  
  919.  
  920.  
  921.  
  922. /************************************************************************/
  923. /*  Function    : split_box                     */
  924. /*  Purpose : Splits a selected box into 2 and reinserts the 2 sub- */
  925. /*        boxes into the frontier list              */
  926. /*  Parameter   :                           */
  927. /*    ptr    - pointer to box to be split               */
  928. /*  Returns     : none                          */
  929. /*  Called by   : sel_palette()                     */
  930. /*  Calls       : find_med(), select_dim(), classify()          */
  931. /************************************************************************/
  932.  
  933. static void split_box(ptr)
  934. struct box *ptr;
  935. {
  936.   int dim, j, i;
  937.   float median;
  938.   struct box *l_child, *r_child;
  939.   int select_dim();
  940.   float find_med();
  941.   void classify();
  942.   
  943.   dim = select_dim(ptr);
  944.   median = find_med(ptr, dim);
  945.  
  946.   /* create 2 child */
  947.   l_child = (struct box *)malloc(sizeof(struct box));
  948.   r_child = (struct box *)malloc(sizeof(struct box));
  949.   
  950.   for (i=RED; i<=BLUE; i++)
  951.     for (j=HI; j<=LO; j++)
  952.     {
  953.       l_child->bnd[i][j] = ptr->bnd[i][j];
  954.       r_child->bnd[i][j] = ptr->bnd[i][j];
  955.     }
  956.   l_child->bnd[dim][HI] = median;
  957.   r_child->bnd[dim][LO] = median;
  958.  
  959.   classify(ptr,l_child);
  960.   classify(ptr,r_child);
  961.  
  962.   r_child->right = ptr->right;
  963.   r_child->left = l_child;
  964.   l_child->right = r_child;
  965.   l_child->left = ptr->left;
  966.   (ptr->left)->right = l_child;
  967.   if (ptr->right != NULL)
  968.     (ptr->right)->left = r_child;
  969. } /* end of split_box */
  970.  
  971.  
  972.  
  973.  
  974.  
  975.  
  976. /************************************************************************/
  977. /*  Function    : assign_color                      */
  978. /*  Purpose : Assigns a color to each box. It computes the average  */
  979. /*        color of all the points in the box            */
  980. /*        Sets up the new_pal buffer. Each color component is   */
  981. /*        shifted left 3 bits because of the truncation when    */
  982. /*        color_pt was set up                   */
  983. /*  Parameter   : none                          */
  984. /*  Returns     : none                          */
  985. /*  Called by   : sel_palette()                     */
  986. /*  Calls       : none                          */
  987. /************************************************************************/
  988.  
  989.  
  990. static void assign_color()
  991. {
  992.   struct box *temp;
  993.   int ent, k, j;
  994.   int c[3];
  995.  
  996.   temp = frontier->right;
  997.   for (ent=0; ent<PALSIZE; ent++)
  998.   {
  999.     for (k=RED; k<=BLUE; k++)
  1000.       c[k] = 0;
  1001.  
  1002. /*
  1003.     printf("Box %d: number of pts %d\n", ent, temp->nmbr_pts);
  1004. */
  1005.  
  1006.     for (j=0; j<temp->nmbr_distinct; j++)
  1007.     {
  1008. /*
  1009.       printf("pt %d:", j);
  1010. */
  1011.       for (k=RED; k<=BLUE; k++)
  1012.       {
  1013. /*
  1014.         printf("%d ",distinct_pt[temp->pts[j]].c[k]);
  1015. */
  1016.     c[k] = c[k] + distinct_pt[temp->pts[j]].c[k]*hist[temp->pts[j]];
  1017.       }
  1018. /*
  1019.       printf("\n");
  1020. */
  1021.     }
  1022.  
  1023.     for (k=RED; k<=BLUE; k++)
  1024.     {
  1025.       c[k] = c[k] / temp->nmbr_pts;
  1026.       new_pal[3*ent+k] = c[k] << 3;
  1027.     }
  1028.     
  1029.     temp = temp->right;
  1030.   } /* end of for entry */
  1031. }
  1032.  
  1033.  
  1034.  
  1035.  
  1036.  
  1037. /************************************************************************/
  1038. /*  Function    : select_dim                        */
  1039. /*  Purpose : Selects the dimension with the largest spread         */
  1040. /*  Parameter   :                           */
  1041. /*    ptr    - pointer to desired box               */
  1042. /*  Returns     : dimension where the box is to be split        */
  1043. /*  Called by   : split_box()                       */
  1044. /*  Calls       : none                          */
  1045. /************************************************************************/
  1046.  
  1047. static int select_dim(ptr)
  1048. struct box *ptr;
  1049. {
  1050.   int i, j, low[3], high[3];
  1051.   int max;
  1052.  
  1053.  
  1054.   for (j=RED; j<=BLUE; j++)
  1055.   {
  1056.     low[j] = distinct_pt[ptr->pts[0]].c[j];
  1057.     high[j] = distinct_pt[ptr->pts[0]].c[j];
  1058.   }
  1059.  
  1060.   for (i=1; i<ptr->nmbr_distinct; i++)
  1061.     for (j=RED; j<=BLUE; j++)
  1062.     {
  1063.       if (low[j] > distinct_pt[ptr->pts[i]].c[j])
  1064.     low[j] = distinct_pt[ptr->pts[i]].c[j];
  1065.       if (high[j] < distinct_pt[ptr->pts[i]].c[j])
  1066.     high[j] = distinct_pt[ptr->pts[i]].c[j];
  1067.     }
  1068.  
  1069.   max = high[RED] - low[RED];
  1070.   i = RED;
  1071.   for (j=GREEN; j<=BLUE; j++)
  1072.     if (max < (high[j] - low[j]))
  1073.     {
  1074.       max = high[j] - low[j];
  1075.       i = j;
  1076.     }
  1077.  
  1078.   return i;
  1079. } /* end of select_dim */
  1080.  
  1081.  
  1082.  
  1083.  
  1084.  
  1085. /************************************************************************/
  1086. /*  Function    : find_med                      */
  1087. /*  Purpose : Finds the point where the box is to be split. It finds*/
  1088. /*        a point such that the 2 new boxes have about the same */
  1089. /*        number of color points.               */
  1090. /*  Parameter   :                           */
  1091. /*    ptr    - pointer to box to be split               */
  1092. /*    dim    - dimension to split box               */
  1093. /*  Returns     : point where the box is to be cut          */
  1094. /*  Called by   : split_box()                       */
  1095. /*  Calls       : next_pt()                     */
  1096. /************************************************************************/
  1097.  
  1098. static float find_med(ptr,dim)
  1099. struct box *ptr;
  1100. int dim;
  1101. {
  1102.   int i, j, count, next, prev;
  1103.   int *rank;
  1104.   float median;
  1105.   int next_pt();
  1106.   void sort();
  1107.  
  1108.   rank = (int *)calloc((unsigned)ptr->nmbr_distinct,sizeof(int));
  1109.   for (i=0; i<ptr->nmbr_distinct; i++)
  1110.     rank[i] = ptr->pts[i];
  1111.  
  1112.   sort(0,ptr->nmbr_distinct-1,dim,rank);
  1113. /*
  1114.   for (i=0; i<ptr->nmbr_distinct; i++)
  1115.     printf("find_med: sorted list is %d\n",distinct_pt[rank[i]].c[dim]);
  1116. */
  1117.   
  1118.  
  1119.   count = 0;
  1120.   i = 0;
  1121.   while ((i < ptr->nmbr_distinct) && (count < ptr->nmbr_pts/2))
  1122.   {
  1123.     next = next_pt(dim, i, rank, ptr->nmbr_distinct);
  1124.     for (j=i; j<next; j++)
  1125.       count = count + hist[rank[j]];
  1126.  
  1127.     prev = i;
  1128.     i = next; 
  1129.   }
  1130.  
  1131.   if (prev == 0)
  1132.   {
  1133.     /* the first distinct point overshot the median */
  1134.     median = (float)distinct_pt[rank[prev]].c[dim] + EPSILON;
  1135.   }
  1136.   else
  1137.     median = (float)distinct_pt[rank[prev-1]].c[dim] + EPSILON;
  1138.    
  1139.  
  1140.   return median;
  1141. } /* end of find_med */
  1142.   
  1143.  
  1144.  
  1145.  
  1146.  
  1147.  
  1148. /************************************************************************/
  1149. /*  Function    : classify                      */
  1150. /*  Purpose : Looks at the color points in the parent and selects   */
  1151. /*        the points that belong to the child           */
  1152. /*  Parameter   :                           */
  1153. /*    ptr    - pointer to parent                    */
  1154. /*    child  - pointer to child box                 */
  1155. /*  Returns     : none                          */
  1156. /*  Called by   : split_box()                       */
  1157. /*  Calls       : none                          */
  1158. /************************************************************************/
  1159.  
  1160. static void classify(ptr, child)
  1161. struct box *ptr, *child;
  1162. {
  1163.   int i, j;
  1164.   int *temp;
  1165.   int distinct, total;
  1166.  
  1167.   temp = (int *)calloc((unsigned)ptr->nmbr_distinct,sizeof(int));
  1168.  
  1169.   distinct = 0;
  1170.   total = 0;
  1171.   for (i=0; i<ptr->nmbr_distinct; i++)
  1172.   {
  1173.     j = ptr->pts[i];
  1174.     if ((((float)distinct_pt[j].c[RED] >= child->bnd[RED][LO]) &&
  1175.          ((float)distinct_pt[j].c[RED] <= child->bnd[RED][HI])) &&
  1176.         (((float)distinct_pt[j].c[GREEN] >= child->bnd[GREEN][LO]) &&
  1177.          ((float)distinct_pt[j].c[GREEN] <= child->bnd[GREEN][HI])) &&
  1178.         (((float)distinct_pt[j].c[BLUE] >= child->bnd[BLUE][LO]) &&
  1179.          ((float)distinct_pt[j].c[BLUE] <= child->bnd[BLUE][HI])))
  1180.     {
  1181.       /* pt is in new box */
  1182.       temp[distinct] = j;
  1183.       distinct++;
  1184.       total = total + hist[j];
  1185.     } /* end of if */
  1186.   } /* end of for i */
  1187.  
  1188.   /* assign points */
  1189.   child->nmbr_pts = total;
  1190.   child->nmbr_distinct = distinct;
  1191.   child->pts = (int *)calloc((unsigned)distinct,sizeof(int));
  1192.   for (i=0; i<distinct; i++)
  1193.     child->pts[i] = temp[i];
  1194.  
  1195. } /* end of classify */
  1196.  
  1197.  
  1198.  
  1199.  
  1200.  
  1201. /************************************************************************/
  1202. /*  Function    : next_pt                       */
  1203. /*  Purpose : Determines the next point that has a different value  */
  1204. /*        from the current point along  a dimension     */
  1205. /*  Parameter   :                           */
  1206. /*    dim    - dimension where box is to be split           */
  1207. /*    i      - index to current point               */
  1208. /*    rank       - sorted list of points to be searched starting from i */
  1209. /*    distinct   - length of sorted list                                */
  1210. /*  Returns     : index of point that has a different value     */
  1211. /*  Called by   : find_med                      */
  1212. /*  Calls       : none                          */
  1213. /************************************************************************/
  1214.  
  1215. static int next_pt(dim, i, rank, distinct)
  1216. int dim, i, rank[], distinct;
  1217. {
  1218.   int j;
  1219.   char old;
  1220.  
  1221.   old = distinct_pt[rank[i]].c[dim];
  1222.   for (j=(i+1); j<distinct; j++)
  1223.     if (distinct_pt[rank[j]].c[dim] != old)
  1224.       break;
  1225.  
  1226.   return j;
  1227. } /* end of next_pt */
  1228.  
  1229.